Section: New Results

Combinatorics and combinatorial geometry

Multinerves and Helly numbers of acyclic families

The nerve of a family of sets is a simplicial complex that records the intersection pattern of its subfamilies. Nerves are widely used in computational geometry and topology, because the nerve theorem guarantees that the nerve of a family of geometric objects has the same topology as the union of the objects, if they form a good cover.

In a joint work with Éric Colin de Verdière (CNRS-ENS) and Grégory Ginot (Univ. Paris 6) we relaxed the good cover assumption to the case where each subfamily intersects in a disjoint union of possibly several homology cells, and we proved a generalization of the nerve theorem in this framework, using spectral sequences from algebraic topology. We then deduced a new topological Helly-type theorem that unifies previous results of Amenta, Kalai and Meshulam, and Matoušek. This Helly-type theorem is used to (re)prove, in a unified way, bounds on transversal Helly numbers in geometric transversal theory.

This work was presented at SoCG 2012 [18] , where it received one of the two “best paper” awards.

Set systems and families of permutations with small traces

In a joint work with Otfried Cheong (KAIST, South Korea) and Cyril Nicaud (Univ. Marne-La-Vallée), we studied two problems of the following flavor: how large can a family of combinatorial objects defined on a finite set be if its number of distinct “projections” on any small subset is bounded? We first consider set systems, where the “projections” is the standard notion of trace, and for which we generalized Sauer's Lemma on the size of set systems with bounded VC-dimension. We then studied families of permutations, where the “projections” corresponds to the notion of containment used in the study of permutations with excluded patterns, and for which we delineated the main growth rates ensured by projection conditions. One of our motivations for considering these questions is the “geometric permutation problem” in geometric transversal theory, a question that has been open for two decades.

This work was published in the European Journal of Combinatorics [13] .

Simplifying inclusion-exclusion formulas

Let $F=\{F_1,F_2,...,F_n\}$ be a family of $n$ sets on a ground set $X$, such as a family of balls in $R^d$. For every finite measure $\mu$ on $X$, such that the sets of $F$ are measurable, the classical inclusion-exclusion formula asserts that $\mu (F_1\cup F_2\cup •••\cup F_n)={\sum }_{I:\varnothing \ne I\subseteq \left[n\right]}{(-1)}^{\left|I\right|+1}\mu \left({\cap }_{i\in I}{F}_i\right)$; that is, the measure of the union is expressed using measures of various intersections. The number of terms in this formula is exponential in $n$, and a significant amount of research, originating in applied areas, has been devoted to constructing simpler formulas for particular families $F$.

In a joint work with Jiří Matoušek, Pavel Paták, Zuzana Safernová and Martin Tancer (Charles Univ., Prague) [22] we provided the apparently first upper bound valid for an arbitrary $F$: we showed that every system $F$ of $n$ sets with $m$ nonempty fields in the Venn diagram admits an inclusion-exclusion formula with $m^{O\left({\left(logn\right)}^2\right)}$ terms and with $\pm 1$ coefficients, and that such a formula can be computed in $m^{O\left({\left(logn\right)}^2\right)}$ expected time. We also constructed systems of $n$ sets on $n$ points for which every valid inclusion-exclusion formula has the sum of absolute values of the coefficients at least $\Omega \left(n^{3/2}\right)$.